/**
 *  @file    LinklistBasicOperate.c
 *  @brief   链式队列的基本操作实现
 *  @details 演示：
 *           1) 使用链表实现队列结构（带头结点）
 *           2) 支持入队、出队、判空、取队头、清空等操作
 *           3) 队列长度获取、遍历打印等功能
 *           4) 入队在尾部，出队从头部（符合先进先出 FIFO）
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025-07-29 15:30
 *  @version 1.0
 */

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

// ------------------------- 类型定义 -------------------------

typedef int EleType;  ///< 队列元素类型

/**
 * @brief 链式队列的节点结构体
 */
typedef struct node {
    EleType data;           ///< 数据域
    struct node *next;      ///< 指针域，指向下一个节点
} node;

/**
 * @brief 链式队列结构体（带头结点）
 */
typedef struct queue{
    node* front;            ///< 指向头结点（不存数据）
    node* rear;             ///< 指向尾节点（存储最新数据）
} queue;

// ------------------------- 基本功能函数 -------------------------

/**
 * @brief 判断链式队列是否为空
 * @param q 指向队列的指针
 * @retval true  队列为空
 * @retval false 队列非空
 */
bool isEmpty(queue *q) {
    return q->front == q->rear;
}

/**
 * @brief 创建新节点并初始化
 * @param value 新节点的数据
 * @return 成功返回新节点指针；失败返回 NULL
 */
node* createNode(int value) {
    node* newNode = (node *) malloc(sizeof(node));
    if (!newNode) {
        printf("Memory allocation failed.\n");
        return NULL;
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

/**
 * @brief 初始化链式队列，生成头结点
 * @param q 指向队列的指针
 * @note front 与 rear 初始都指向头结点
 */
void initQueue(queue *q) {
    node *newNode = createNode(0);
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
    }
    if (newNode == NULL) return;
    q->front = q->rear = newNode;
}

/**
 * @brief 入队操作（尾插法）
 * @param q     指向队列的指针
 * @param value 要入队的元素值
 */
void inQueueByTail(queue *q, int value) {
    node *newNode = createNode(value);
    if (newNode == NULL) return;
    q->rear->next = newNode;
    q->rear = newNode;
}

/**
 * @brief 出队操作（头部出队）
 * @param q     指向队列的指针
 * @param value 用于保存出队的元素值
 * @note 若队列为空则无操作
 */
void deQueueByTail(queue *q, int *value) {
    if (isEmpty(q)) return;

    node *temp = q->front->next;     // 第一个数据节点
    *value = temp->data;

    q->front->next = temp->next;     // 脱链
    if (q->rear == temp) {
        q->rear = q->front;          // 若删除的是唯一节点，rear 回退到头结点
    }
    free(temp);
}

/**
 * @brief 清空链式队列（不释放头结点）
 * @param q 指向队列的指针
 */
void clearQueue(queue *q) {
    if (isEmpty(q)) return;

    node *p = q->front->next;
    while (p) {
        node *temp = p;
        p = p->next;
        free(temp);
    }
    q->front->next = NULL;
    q->rear = q->front;
}

/**
 * @brief 打印当前队列所有元素（从 front→rear）
 * @param q 指向队列的指针
 */
void printQueue(queue *q) {
    if (isEmpty(q)) return;

    node *cur = q->front->next;
    while (cur) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 查看队头元素（不出队）
 * @param q     指向队列的指针
 * @param value 用于保存队头元素的变量地址
 */
void peek(queue *q, int *value) {
    if (isEmpty(q)) return;
    *value = q->front->next->data;
}

/**
 * @brief 获取当前队列的长度
 * @param q 指向队列的指针
 * @return 队列中有效数据节点的个数
 */
int getLength(queue *q) {
    int length = 0;
    if (isEmpty(q)) return length;

    node *cur = q->front->next;
    while (cur) {
        cur = cur->next;
        length++;
    }
    return length;
}

// ------------------------- 主函数测试 -------------------------

/**
 * @brief 测试链式队列的基本操作
 */
int main() {
    queue q;
    initQueue(&q);                          // 初始化

    inQueueByTail(&q, 10);
    inQueueByTail(&q, 20);
    inQueueByTail(&q, 30);
    inQueueByTail(&q, 40);

    EleType val;
    peek(&q, &val);
    printf("peek: %d\n", val);             // 输出 10

    printQueue(&q);                         // 输出全部元素

    deQueueByTail(&q, &val);
    printf("dequeue: %d\n", val);          // 输出 10

    printQueue(&q);                         // 输出 20 30 40

    printf("length: %d\n", getLength(&q)); // 输出 3

    clearQueue(&q);                         // 清空队列

    return 0;
}
